package master;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *
 * 删除链表中的重复元素2
 *
 * @author chenyw
 * @date 2022/7/28 20:16
 */
public class M82deleteDuplicates {

    // 一次遍历. 使用一个变量记录重读元素的第一个值
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                int val = cur.val;
                while (cur != null && cur.val == val) {
                    cur = cur.next;
                }
                //这个时候掷筛改变了pre的next指向，但是并没有移动pre，next指向在下次循环的时候可能还会发生改变
                pre.next = cur;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dummyNode.next;
    }

/*    //map解法
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Map<Integer, Integer> map = new HashMap<>();
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode p = head;
        while (p != null) {
            map.put(p.val, map.getOrDefault(p.val, 0) + 1);
            p = p.next;
        }
        ListNode pre = dummyNode;
        p = head;
        while (p != null) {
            while (p != null && map.get(p.val) > 1) {
                p = p.next;
            }
            pre.next = p;
            pre = p;
            if (p != null) {
                p = p.next;
            }

        }
        return dummyNode.next;
    }*/
}
